// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
#include <vector>
using namespace std;
class Solution
{
private:
public:
    // 中序
    void load_arr(TreeNode *root, vector<int> &arr)
    {
        if (!root)
            return;
        load_arr(root->left, arr);
        arr.push_back(root->val);
        load_arr(root->right, arr);
    }
    bool findTarget(TreeNode *root, int k)
    {
        vector<int> arr;
        load_arr(root, arr);
        // 双指针
        int l(0), r(arr.size() - 1);
        while (l < r)
        {
            int add = arr[l] + arr[r];
            if (add == k)
                return true;
            add > k ? r-- : l++;
        }
        return false;
    }
};
#include <unordered_set>
using namespace std;
class Solution
{
private:
public:
    // 中序
    void load_set(TreeNode *root, unordered_set<int> &st)
    {
        if (!root)
            return;
        load_set(root->left, st);
        st.insert(root->val);
        load_set(root->right, st);
    }
    bool findTarget(TreeNode *root, int k)
    {
        unordered_set<int> st;
        load_set(root, st);
        // 哈希
        for (auto it = st.begin(); it != st.end(); it++)
        {
            // 找k-val即可
            auto find_ret = st.find(k - *it);
            if (find_ret != st.end() && find_ret != it)
                return true;
        }
        return false;
    }
};